/*
 ------------------------------------------------------------------------------
 Copyright (C) 2013 Eternal Games.

 This file is part of the EternalTech source code.

 The EternalTech source code is free software; you can redistribute it and/or
 modify it under the terms of the GNU General Public License as published by
 the Free Software Foundation; either version 2 of the License, or (at your
 option) any later version.

 The EternalTech source code is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
 or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
 more details.

 You should have received a copy of the GNU General Public License along with
 the EternalTech source code; if not, write to the Free Software Foundation, Inc.,
 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 ------------------------------------------------------------------------------
*/


//
// r_surface.cpp - surface list generation
//


#include "r_local.h"


/*
 ==================
 R_AddDrawSurface
 ==================
*/
static void R_AddDrawSurface (dsType_t type, dsGeometry_t *geometry, entity_t *entity, material_t *material, uint bits){

	drawSurface_t	*ds;
	int				index;

	if (material->coverage != MC_TRANSLUCENT)
		index = 0;
	else {
		if (material->sort < SORT_REFRACTIVE)
			index = 1;
		else if (material->sort < SORT_POST_PROCESS)
			index = 2;
		else
			index = 3;
	}

	// Add a new draw surface
	if (rg.numDrawSurfaces[index] == rg.maxDrawSurfaces[index]){
		Com_DPrintf(S_COLOR_YELLOW "R_AddDrawSurface: overflow\n");
		return;
	}

	rg.drawSurfaces[index][rg.numDrawSurfaces[index]++] = ds = (drawSurface_t *)R_FrameAlloc(sizeof(drawSurface_t));

	// Fill it in
	ds->type = type;
	ds->geometry = geometry;

	ds->entity = entity;
	ds->material = material;

	ds->sort = (material->sort << DS_SHIFT_SORT) | (entity->index << DS_SHIFT_ENTITY) | (material->index << DS_SHIFT_MATERIAL) | type;
	ds->bits = bits;
}


/*
 ==============================================================================

 WORLD SURFACES

 ==============================================================================
*/


/*
 ==================
 R_AddSurface

 FIXME: make sure SURF_PLANEBACK is used correct
 ==================
*/
static void R_AddSurface (surface_t *surface, material_t *material, entity_t *entity, const glqVec3 &viewOrigin, int cullBits){

	// Cull face
	if (!r_skipFaceCulling->integerValue && surface->plane && material->deform == DFRM_NONE){
		if (material->cullType == CT_FRONT_SIDED){
			if (!(surface->flags & SURF_PLANEBACK)){
				if (surface->plane->PointOnSide(viewOrigin) != PLANESIDE_FRONT)
					return;
			}
		}
		else if (material->cullType == CT_BACK_SIDED){
				if (surface->plane->PointOnSide(viewOrigin) != PLANESIDE_BACK)
					return;
		}
	}

	// Cull bounds
	if (cullBits != CULL_IN){
		if (entity == rg.scene->worldEntity){
			if (R_CullBounds(surface->bounds, cullBits) == CULL_OUT)
				return;
		}
		else {
			if (R_CullLocalBounds(surface->bounds, entity->e.origin, entity->e.axis, cullBits) == CULL_OUT)
				return;
		}
	}

	// Mark as visible for this view
	surface->viewCount = rg.viewCount;

	// Add a subview surface if needed
	if (material->subviewType != ST_NONE){
		if (!R_AddSubviewSurface(DS_SURFACE, surface, entity, material))
			return;
	}

	// Add the draw surface
	R_AddDrawSurface(DS_SURFACE, surface, entity, material, 0);
}

/*
 ==================
 R_RecursiveWorldNode
 ==================
*/
static void R_RecursiveWorldNode (node_t *node, int cullBits){

	leaf_t		*leaf;
	surface_t	*surface, **mark;
	int			i;

	while (1){
		// Check for solid content
		if (node->contents == CONTENT_SOLID)
			return;

		// Check visibility
		if (node->visCount != rg.visCount)
			return;

		// Cull
		if (cullBits != CULL_IN){
			cullBits = R_CullBounds(node->bounds, cullBits);

			if (cullBits == CULL_OUT)
				return;
		}

		// Mark as visible for this view
		node->viewCount = rg.viewCount;

		if (node->contents < 0)
			break;		// Leaf node

		// Recurse down the children, front side first
		R_RecursiveWorldNode(node->children[0], cullBits);

		// Tail recurse
		node = node->children[1];
	}

	// Leaf node
	leaf = (leaf_t *)node;

	if (!leaf->numMarkSurfaces)
		return;

	rg.pc.leafs++;

	// Development tool
	if (r_showLeafBounds->integerValue == 2)
		R_DebugBounds(colorWhite, leaf->bounds, true, rg.viewParms.viewType);
	else if (r_showLeafBounds->integerValue == 1)
		R_DebugBounds(colorWhite, leaf->bounds, false, rg.viewParms.viewType);

	// Add to the vis bounds
	rg.viewParms.visBounds += leaf->bounds;

	// If it has a single surface, no need to cull again
	if (leaf->numMarkSurfaces == 1)
		cullBits = CULL_IN;

	// Add all the surfaces
	for (i = 0, mark = leaf->firstMarkSurface; i < leaf->numMarkSurfaces; i++, mark++){
		surface = *mark;

		if (surface->checkCount == rg.checkCount)
			continue;		// Already added this surface from another leaf
		surface->checkCount = rg.checkCount;

		// Add the surface
		R_AddSurface(surface, surface->texInfo->material, rg.scene->worldEntity, rg.renderView.origin, cullBits);
	}
}

/*
 ==================
 R_AddWorldSurfaces
 ==================
*/
static void R_AddWorldSurfaces (){

	if (!rg.viewParms.primaryView)
		return;

	// Bump check count
	rg.checkCount++;

	// Mark the world entity as visible for this view
	rg.scene->worldEntity->viewCount = rg.viewCount;

	// Clear the vis bounds
	rg.viewParms.visBounds.Clear();

	// Mark visible leaves
	R_MarkLeaves();

	// Recurse down the BSP tree
	if (r_skipCulling->integerValue)
		R_RecursiveWorldNode(rg.world->nodes, CULL_IN);
	else
		R_RecursiveWorldNode(rg.world->nodes, rg.viewParms.planeBits);

	// Now that we have the vis bounds, set the far clip plane
	R_SetFarClip();
}


/*
 ==============================================================================

 ENTITY SURFACES

 ==============================================================================
*/


/*
 ==================
 
 FIXME: we need a sphere before this can contiue
 ==================
*/
static void R_AddInlineModelSurfaces (entity_t *entity){

	inlineModel_t	*model = (inlineModel_t *)entity->e.model->data;
	surface_t		*surface;
	material_t		*material;
	glqVec3			viewOrigin;
	int				cullBits;
	int				i;

	// Cull
	cullBits = 0;

	// Transform view origin into local space
	R_WorldPointToLocal(rg.renderView.origin, viewOrigin, entity->e.origin, entity->e.axis);

	// Mark as visible for this view
	entity->viewCount = rg.viewCount;

	rg.pc.entities++;

	// If it has a single surface, no need to cull again
	if (model->numSurfaces == 1)
		cullBits = CULL_IN;

	// Add all the surfaces
	for (i = 0, surface = model->surfaces; i < model->numSurfaces; i++, surface++){
		// Get the material
		if (entity->e.material)
			material = entity->e.material;
		else
			material = R_RemapMaterialBySkin(surface->texInfo->material, entity->e.skin);

		// Add the surface
		R_AddSurface(surface, material, entity, viewOrigin, cullBits);
	}
}

/*
 ==================
 
 FIXME: we need the renderEntity_t sphere/bounds
 FIXME: how should we cull the surface bounds?, the frames and all that...
 ==================
*/
static void R_AddModelSurfaces (entity_t *entity){

	aliasMdl_t			*model = (aliasMdl_t *)entity->e.model->data;
	aliasMdlSurface_t	*surface;
	aliasMdlFrame_t		*frame;
	material_t			*material;
	int					cullBits, cullBitsSurf;
	int					i;

	// Check frames
	if ((entity->e.frame < 0 || entity->e.frame >= model->numFrames) || (entity->e.oldFrame < 0 || entity->e.oldFrame >= model->numFrames)){
		Com_DPrintf(S_COLOR_YELLOW "R_AddAliasModel: no such frame %i to %i (%s)\n", entity->e.frame, entity->e.oldFrame, entity->e.model->name);

		entity->e.frame = 0;
		entity->e.oldFrame = 0;
	}

	// Cull
	if (r_skipEntityCulling->integerValue || entity->e.depthHack)
		cullBits = CULL_IN;
	else {

	}

	// Mark as visible for this view
	entity->viewCount = rg.viewCount;

	rg.pc.entities++;

	// If it has a single surface, no need to cull again
	if (model->numSurfaces == 1)
		cullBits = CULL_IN;

	// Add all the surfaces
	for (i = 0, surface = model->surfaces; i < model->numSurfaces; i++, surface++){
		// Cull

		// Get the material
		if (entity->e.material)
			material = entity->e.material;
		else
			material = R_RemapMaterialBySkin(surface->materials[0].material, entity->e.skin);

		// Add a subview surface if needed
		if (material->subviewType != ST_NONE){
			if (!R_AddSubviewSurface(DS_MODEL, surface, entity, material))
				continue;
		}

		// Add the draw surface
		R_AddDrawSurface(DS_MODEL, surface, entity, material, 0);
	}
}

/*
 ==================
 
 ==================
*/
static void R_AddSpriteModelSurfaces (entity_t *entity){

}

/*
 ==================
 R_AddSpriteSurface
 ==================
*/
static void R_AddSpriteSurface (entity_t *entity){

	material_t	*material;

	// Cull
	if (!r_skipEntityCulling->integerValue && !entity->e.depthHack){
		if (R_CullSphere(glqSphere(entity->e.origin, entity->e.spriteRadius * M_SQRT_TWO), rg.viewParms.planeBits) == CULL_OUT)
			return;
	}

	// Mark as visible for this view
	entity->viewCount = rg.viewCount;

	rg.pc.entities++;

	// Get the material
	if (entity->e.material)
		material = entity->e.material;
	else
		material = rg.defaultMaterial;

	// Add the draw surface
	R_AddDrawSurface(DS_SPRITE, NULL, entity, material, 0);
}

/*
 ==================
 R_AddBeamSurface
 ==================
*/
static void R_AddBeamSurface (entity_t *entity){

	material_t	*material;

	// Cull
	if (!r_skipEntityCulling->integerValue && !entity->e.depthHack){
		if (R_CullLine(entity->e.origin, entity->e.beamEnd, entity->e.beamWidth * 0.5f, rg.viewParms.planeBits) == CULL_OUT)
			return;
	}

	// Mark as visible for this view
	entity->viewCount = rg.viewCount;

	rg.pc.entities++;

	// Get the material
	if (entity->e.material)
		material = entity->e.material;
	else
		material = rg.defaultMaterial;

	// Add the draw surface
	R_AddDrawSurface(DS_BEAM, NULL, entity, material, 0);
}

/*
 ==================
 R_AddEntitySurfaces
 ==================
*/
static void R_AddEntitySurfaces (){

	entity_t	*entity;

	if (r_skipEntities->integerValue)
		return;

	for (entity = rg.scene->activeEntity.next; entity != &rg.scene->activeEntity; entity = entity->next){
		if (entity == rg.scene->worldEntity)
			continue;		// World entity

		// Development tool
		if (r_singleEntity->integerValue != -1){
			if (r_singleEntity->integerValue != entity->index)
				continue;
		}

		// Check for view suppression
		if (!r_skipSuppress->integerValue){
			if (!(entity->e.allowInView & rg.viewParms.viewType))
				continue;
		}

		// Add the entity
		switch (entity->e.type){
		case RE_MODEL:
			if (!entity->e.model || entity->e.model->type == MODEL_BAD){
				R_AddDrawSurface(DS_NULL, NULL, entity, rg.defaultMaterial, 0);
				break;
			}

			switch (entity->e.model->type){
			case MODEL_INLINE:
				R_AddInlineModelSurfaces(entity);
				break;
			case MODEL_MDL:
			case MODEL_MD3:
				R_AddModelSurfaces(entity);
				break;
			case MODEL_SPRITE:
				R_AddSpriteModelSurfaces(entity);
				break;
			default:
				Com_Error(false, "R_AddEntitySurfaces: bad model type (%i)", entity->e.model->type);
			}

			break;
		case RE_SPRITE:
			R_AddSpriteSurface(entity);
			break;
		case RE_BEAM:
			R_AddBeamSurface(entity);
			break;
		default:
			Com_Error(false, "R_AddEntitySurfaces: bad entity type (%i)", entity->e.type);
		}
	}
}


/*
 ==============================================================================

 PARTICLE SURFACES

 ==============================================================================
*/


/*
 ==================
 
 ==================
*/
static void R_AddParticleSurfaces (){

}


/*
 ==============================================================================

 DECAL SURFACES

 ==============================================================================
*/


/*
 ==================
 
 ==================
*/
static void R_AddDecalSurfaces (){

}


// ============================================================================



/*
 ==================
 R_SortDrawSurfaces
 ==================
*/
static void R_SortDrawSurfaces (int numDrawSurfaces, drawSurface_t **drawSurfaces){

	int		lo, loGuy, loStack[32];
	int		hi, hiGuy, hiStack[32];
	int		mid, count, stackDepth;
	int		i, max;

	if (r_skipSorting->integerValue)
		return;

	if (numDrawSurfaces < 2)
		return;

	// Initialize stack
	stackDepth = 0;

	// Initialize limits
	lo = 0;
	hi = numDrawSurfaces - 1;

	// Entry point for recursion
recurse:

	// Number of elements to sort
	count = (hi - lo) + 1;

	// Below a certain count, it is faster to use insertion sort
	if (count <= 8){
		while (hi > lo){
			max = lo;

			for (i = lo + 1; i <= hi; i++){
				if (drawSurfaces[i]->sort > drawSurfaces[max]->sort)
					max = i;
			}

			// Swap elements
			Swap(drawSurfaces[max], drawSurfaces[hi]);

			hi--;
		}
	}
	else {
		// Pick a partitioning element
		mid = lo + (count >> 1);

		// Sort the first, middle, and last elements into order
		if (drawSurfaces[lo]->sort > drawSurfaces[mid]->sort)
			Swap(drawSurfaces[lo], drawSurfaces[mid]);
		if (drawSurfaces[lo]->sort > drawSurfaces[hi]->sort)
			Swap(drawSurfaces[lo], drawSurfaces[hi]);
		if (drawSurfaces[mid]->sort > drawSurfaces[hi]->sort)
			Swap(drawSurfaces[mid], drawSurfaces[hi]);

		// Now partition the array into three pieces
		loGuy = lo;
		hiGuy = hi;

		while (1){
			if (mid > loGuy){
				do {
					loGuy++;
				} while (loGuy < mid && drawSurfaces[loGuy]->sort <= drawSurfaces[mid]->sort);
			}
			if (mid <= loGuy){
				do {
					loGuy++;
				} while (loGuy <= hi && drawSurfaces[loGuy]->sort <= drawSurfaces[mid]->sort);
			}

			do {
				hiGuy--;
			} while (hiGuy > mid && drawSurfaces[hiGuy]->sort > drawSurfaces[mid]->sort);

			if (hiGuy < loGuy)
				break;

			// Swap elements
			Swap(drawSurfaces[loGuy], drawSurfaces[hiGuy]);

			if (mid == hiGuy)
				mid = loGuy;
		}

		// Find adjacent elements equal to the partition element
		hiGuy++;

		if (mid < hiGuy){
			do {
				hiGuy--;
			} while (hiGuy > mid && drawSurfaces[hiGuy]->sort == drawSurfaces[mid]->sort);
		}
		if (mid >= hiGuy){
			do {
				hiGuy--;
			} while (hiGuy > lo && drawSurfaces[hiGuy]->sort == drawSurfaces[mid]->sort);
		}

		// We've finished the partition, now we want to sort the subarrays
		if (hiGuy - lo >= hi - loGuy){
			if (lo < hiGuy){
				loStack[stackDepth] = lo;
				hiStack[stackDepth] = hiGuy;

				stackDepth++;
			}

			if (loGuy < hi){
				lo = loGuy;
				goto recurse;
			}
		}
		else {
			if (loGuy < hi){
				loStack[stackDepth] = loGuy;
				hiStack[stackDepth] = hi;

				stackDepth++;
			}

			if (lo < hiGuy){
				hi = hiGuy;
				goto recurse;
			}
		}
	}

	// We have sorted the array, except for any pending sorts on the stack.
	// Check if there are any, and do them.
	if (--stackDepth >= 0){
		lo = loStack[stackDepth];
		hi = hiStack[stackDepth];

		goto recurse;
	}
}

/*
 ==================
 R_SetupDrawSurfaces
 ==================
*/
void R_SetupDrawSurfaces (int numDrawSurfaces, drawSurface_t **drawSurfaces){

	drawSurface_t	*ds;
	entity_t		*entity;
	material_t		*material, *referenceMaterial;
	float			*registers, *referenceRegisters;
	float			materialParms[MAX_MATERIAL_PARMS];
	uint			sort;
	int				i;

	// Sort the draw surfaces by sort type, then entity, then material, then
	// surface type
	R_SortDrawSurfaces(numDrawSurfaces, drawSurfaces);

	// Clear the state
	entity = NULL;
	material = NULL;

	sort = 0;

	// Run through the draw surfaces
	for (i = 0; i < numDrawSurfaces; i++){
		ds = drawSurfaces[i];

		// Check if the state changed
		if (ds->sort != sort){
			// Check if either the entity or the material changed
			if (ds->entity != entity || ds->material != material){
				// See if we have a reference material
				if (ds->entity->e.referenceMaterial == NULL){
					// Evaluate material registers
					registers = (float *)R_FrameAlloc(ds->material->numRegisters * sizeof(float));

					R_EvaluateRegisters(ds->material, rg.viewParms.floatTime, ds->entity->e.materialParms, ds->entity->e.soundEmitterHandle, registers);
				}
				else {
					// A reference material will take the calculated stage
					// color value from another material and use that for the
					// parm0-parm3 of the current material, which allows a
					// stage of a light model and light flare to pick up
					// different flashing tables from different light materials
					referenceMaterial = ds->entity->e.referenceMaterial;

					// Evaluate reference material registers
					referenceRegisters = (float *)R_FrameAlloc(referenceMaterial->numRegisters * sizeof(float));

					R_EvaluateRegisters(referenceMaterial, rg.viewParms.floatTime, ds->entity->e.materialParms, ds->entity->e.soundEmitterHandle, referenceRegisters);

					// Set up the material parms
					materialParms[0] = referenceRegisters[referenceMaterial->stages->colorStage.registers[0]];
					materialParms[1] = referenceRegisters[referenceMaterial->stages->colorStage.registers[1]];
					materialParms[2] = referenceRegisters[referenceMaterial->stages->colorStage.registers[2]];
					materialParms[3] = referenceRegisters[referenceMaterial->stages->colorStage.registers[3]];
					materialParms[4] = ds->entity->e.materialParms[4];
					materialParms[5] = ds->entity->e.materialParms[5];
					materialParms[6] = ds->entity->e.materialParms[6];
					materialParms[7] = ds->entity->e.materialParms[7];

					// Evaluate material registers
					registers = (float *)R_FrameAlloc(ds->material->numRegisters * sizeof(float));

					R_EvaluateRegisters(ds->material, rg.viewParms.floatTime, materialParms, ds->entity->e.soundEmitterHandle, registers);
				}
			}

			// Set the state
			entity = ds->entity;
			material = ds->material;
		}

		// Set the registers
		ds->registers = registers;
	}
}

/*
 ==================
 R_AllocDrawSurfaces
 ==================
*/
void R_AllocDrawSurfaces (){

	rg.numDrawSurfaces[0] = rg.firstDrawSurface[0] = 0;
	rg.numDrawSurfaces[1] = rg.firstDrawSurface[1] = 0;
	rg.numDrawSurfaces[2] = rg.firstDrawSurface[2] = 0;
	rg.numDrawSurfaces[3] = rg.firstDrawSurface[3] = 0;

	rg.maxDrawSurfaces[0] = MAX_DRAW_SURFACES;
	rg.maxDrawSurfaces[1] = MAX_DRAW_SURFACES >> 1;
	rg.maxDrawSurfaces[2] = MAX_DRAW_SURFACES >> 1;
	rg.maxDrawSurfaces[3] = MAX_DRAW_SURFACES >> 6;

	rg.drawSurfaces[0] = (drawSurface_t **)R_FrameAlloc(rg.maxDrawSurfaces[0] * sizeof(drawSurface_t *));
	rg.drawSurfaces[1] = (drawSurface_t **)R_FrameAlloc(rg.maxDrawSurfaces[1] * sizeof(drawSurface_t *));
	rg.drawSurfaces[2] = (drawSurface_t **)R_FrameAlloc(rg.maxDrawSurfaces[2] * sizeof(drawSurface_t *));
	rg.drawSurfaces[3] = (drawSurface_t **)R_FrameAlloc(rg.maxDrawSurfaces[3] * sizeof(drawSurface_t *));
}

/*
 ==================
 R_GenerateDrawSurfaces
 ==================
*/
void R_GenerateDrawSurfaces (){

	// Add the draw surfaces
	R_AddWorldSurfaces();
	R_AddEntitySurfaces();
	R_AddParticleSurfaces();
	R_AddDecalSurfaces();

	// Set up the draw surfaces
	rg.viewParms.numDrawSurfaces[0] = rg.numDrawSurfaces[0] - rg.firstDrawSurface[0];
	rg.viewParms.numDrawSurfaces[1] = rg.numDrawSurfaces[1] - rg.firstDrawSurface[1];
	rg.viewParms.numDrawSurfaces[2] = rg.numDrawSurfaces[2] - rg.firstDrawSurface[2];
	rg.viewParms.numDrawSurfaces[3] = rg.numDrawSurfaces[3] - rg.firstDrawSurface[3];

	rg.viewParms.drawSurfaces[0] = rg.drawSurfaces[0] + rg.firstDrawSurface[0];
	rg.viewParms.drawSurfaces[1] = rg.drawSurfaces[1] + rg.firstDrawSurface[1];
	rg.viewParms.drawSurfaces[2] = rg.drawSurfaces[2] + rg.firstDrawSurface[2];
	rg.viewParms.drawSurfaces[3] = rg.drawSurfaces[3] + rg.firstDrawSurface[3];

	rg.pc.surfaces += rg.viewParms.numDrawSurfaces[0] + rg.viewParms.numDrawSurfaces[1] + rg.viewParms.numDrawSurfaces[2] + rg.viewParms.numDrawSurfaces[3];

	R_SetupDrawSurfaces(rg.viewParms.numDrawSurfaces[0], rg.viewParms.drawSurfaces[0]);
	R_SetupDrawSurfaces(rg.viewParms.numDrawSurfaces[1], rg.viewParms.drawSurfaces[1]);
	R_SetupDrawSurfaces(rg.viewParms.numDrawSurfaces[2], rg.viewParms.drawSurfaces[2]);
	R_SetupDrawSurfaces(rg.viewParms.numDrawSurfaces[3], rg.viewParms.drawSurfaces[3]);

	// The next view rendered in this frame will tack on after this one
	rg.firstDrawSurface[0] = rg.numDrawSurfaces[0];
	rg.firstDrawSurface[1] = rg.numDrawSurfaces[1];
	rg.firstDrawSurface[2] = rg.numDrawSurfaces[2];
	rg.firstDrawSurface[3] = rg.numDrawSurfaces[3];
}